package cn.caplike.demo.algorithm.sort;

/**
 * Description: 快速排序<br>
 * 基本思想: 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。<br>
 * Details: 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：<br>
 * 从数列中挑出一个元素，称为 “基准”（pivot）；<br>
 * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；<br>
 * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。<br>
 * 最佳情况: T(n) = O(nlog<sup>n</sup>)   最差情况：T(n) = O(n<sup>2</sup>)   平均情况：T(n) = O(n<sup>n</sup>)<br>
 * Reference: https://blog.csdn.net/shujuelin/article/details/82423852
 *
 * @author LiKe
 * @version 1.0.0
 * @date 2020-09-12 13:48
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4, 0, 2, 5, 8};

        quickSort(arr, 0, arr.length - 1);

        for (int i : arr) System.out.print(i + "\t");
    }

    /**
     * @param arr      待排序列
     * @param startIdx 待排序列起始位置
     * @param endIdx   待排序列结束位置
     */
    private static void quickSort(int[] arr, int startIdx, int endIdx) {
        if (startIdx >= endIdx) {
            return;
        }

        int currentStartIdx = startIdx;
        int currentEndIdx = endIdx;
        //待排序的第一个元素作为基准值
        int key = arr[currentStartIdx];

        //从左右两边交替扫描，直到left = currentEndIdx
        while (currentStartIdx < currentEndIdx) {
            while (currentEndIdx > currentStartIdx && arr[currentEndIdx] >= key) {
                //从右往左扫描，找到第一个比基准值小的元素
                currentEndIdx--;
            }

            //找到这种元素将arr[currentEndIdx]放入arr[currentStartIdx]中
            arr[currentStartIdx] = arr[currentEndIdx];

            while (currentStartIdx < currentEndIdx && arr[currentStartIdx] <= key) {
                //从左往右扫描，找到第一个比基准值大的元素
                currentStartIdx++;
            }

            //找到这种元素将arr[currentStartIdx]放入arr[currentEndIdx]中
            arr[currentEndIdx] = arr[currentStartIdx];
        }

        for (int i : arr) System.out.print(i + "\t");
        System.out.println(" (currentStartIdx: " + currentStartIdx + ") ");

        //基准值归位
        arr[currentStartIdx] = key;
        //对基准值左边的元素进行递归排序
        quickSort(arr, startIdx, currentStartIdx - 1);
        //对基准值右边的元素进行递归排序。
        quickSort(arr, currentEndIdx + 1, endIdx);
    }
}
